package solutions;

import common.LinkNode;

/**
 * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
 * Created by Wongy on 2018/3/26.
 */
public class Solution17 {

    public static void main(String[] args) {
        LinkNode linkNode4 = new LinkNode(8);
        LinkNode linkNode3 = new LinkNode(6, linkNode4);
        LinkNode linkNode2 = new LinkNode(4, linkNode3);
        LinkNode linkNode1 = new LinkNode(2, linkNode2);
        LinkNode linkNode0 = new LinkNode(0, linkNode1);

        LinkNode node4 = new LinkNode(9);
        LinkNode node3 = new LinkNode(7, node4);
        LinkNode node2 = new LinkNode(5, node3);
        LinkNode node1 = new LinkNode(3, node2);
        LinkNode node0 = new LinkNode(1, node1);

        LinkNode linkNode = merge(linkNode0, node0);
        System.out.println(linkNode);
    }

    private static LinkNode merge(LinkNode list1, LinkNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        LinkNode linkNode = null;
        linkNode = list1.value < list2.value ? list1 : list2;
        linkNode.next = list1.value < list2.value ? merge(list1.next, list2) : merge(list1, list2.next);
        return linkNode;
    }


}
